import LinkedList from './01_实现单向链表LinkedList'
import { DoublyNode, Node } from './LinkedNode';

class DoublyLinkedList<T> extends LinkedList<T>{
    protected head: DoublyNode<T> | null = null
    protected tail: DoublyNode<T> | null = null

    //在尾部追加元素
    append(value: T): void {
        const newNode = new DoublyNode<T>(value)
        // 如果当前的链表没有数据
        if(!this.head){
            this.head = newNode;
            this.tail = newNode;
        }else{
            this.tail!.next = newNode;
            // 不能将一个父类的对象,赋值给一个子类的类型
            // 可以将一个子类的类型, 赋值给一个父类的类型(多态)
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
    }

    // 新增的prepend方法，在头部追加元素
    prepend(value:T){
        const newNode = new DoublyNode<T>(value)
        // 如果当前的链表没有数据
        if(!this.head){
            this.head = newNode;
            this.tail = newNode;
        }else{
            //新节点的下一个节点为之前的头结点
            newNode.next = this.head;
            // 之前头结点的上一个节点为新节点（新头节点）
            this.head.prev = newNode;
            // 让this.head新添加的节点
            this.head = newNode;
        }
        this.length++;
    }

    // 反向遍历链表
    postTraverse(){
        let current = this.tail;
        let values: T[] = [];
        while(current){
            values.push(current.value)
            current = current.prev;
        }
        console.log(values.join('->'));
    }

    // 根据索引插入元素
    insert(value: T, position: number): boolean {
        if(position < 0 || position > this.length) return false; 

        if(position === 0){
            this.prepend(value)
        }else if(position === this.length){
            this.append(value)
        }else{
            const newNode = new DoublyNode<T>(value)
            // 这里调用的父级的getNode方法（其返回的current是Node<T>）不存在prev ,但是这里是双向链表，节点都是存在prev的所以这里通过as 将其类型进行定义
            let current = this.getNode(position) as DoublyNode<T>;
            // 双向链表的插入,相当于连接了四条线
            // 这里比如插入位置是3
            // 先将2主动和3连接
            current.prev!.next = newNode
              // 在将3主动和2连接
            newNode.prev = current.prev;
             // 将3主动和4连接
            newNode.next = current;
             // 将4主动和3连接
            current.prev = newNode
            // current.pre = newNode;
            this.length++;
        }
        return true;
    }

    // 根据索引删除元素
    removeAt(position: number): T | null {
        if(position < 0 || position >= this.length) return null; 

        let current = this.head;
        if(position === 0){
            if(this.length === 1){
                this.head = null;
                this.tail = null;
            }else{
                this.head = this.head!.next;
                this.head!.prev = null
            }
        }else if(position === this.length -1){
            current = this.tail;
            this.tail = this.tail!.prev;
            this.tail!.next = null
        }else{
            let current = this.getNode(position) as DoublyNode<T>;
            current.prev!.next = current.next;
            current.next!.prev = current.prev;
        }

        this.length -- ;
        return current?.value ?? null;
    }
}

const dLinkedList = new DoublyLinkedList<string>()

// 测试append方法

console.log('------------append/prepend-------------')
dLinkedList.append('aaa')
dLinkedList.append('bbb')
dLinkedList.append('ccc')
dLinkedList.append('ddd')

dLinkedList.prepend('abc')
dLinkedList.prepend('cba')


dLinkedList.traverse()
dLinkedList.postTraverse()


console.log('------------insert-------------')
dLinkedList.insert('why',0)
dLinkedList.insert('kobe',7)
dLinkedList.insert('james',3)
dLinkedList.traverse()

console.log('------------removeAt-------------')
dLinkedList.removeAt(0)
dLinkedList.removeAt(7)
dLinkedList.removeAt(2)
dLinkedList.traverse()
// dLinkedList.postTraverse()


